|
In graph theory, a path in a graph is a finite or infinite sequence of edges which connect a sequence of vertices which, by most definitions, are all distinct from one another. In a directed graph, a directed path (sometimes called dipath〔Graph Structure Theory: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Held June 22 to July 5, 1991,, (p.205 )〕) is again a sequence of edges (or arcs) which connect a sequence of vertices, but with the added restriction that the edges all be directed in the same direction. Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See e.g. Bondy and Murty (1976), Gibbons (1985), or Diestel (2005). Korte et al. (1990) cover more advanced algorithmic topics concerning paths in graphs. == Definitions == A path is a trail in which all vertices (except possibly the first and last) are distinct. A trail is a walk in which all edges are distinct. A walk of length in a graph is an alternating sequence of vertices and edges, , which begins and ends with vertices. If the graph is directed, then is an arc from to . An infinite path is an alternating sequence of the same type described here, but with no first or last vertex, and a semi-infinite path (also ray) has a first vertex, , but no last vertex. Most authors require that all of the edges and vertices be distinct from one another. A weighted graph associates a value (''weight'') with every edge in the graph. The ''weight of a path'' in a weighted graph is the sum of the weights of the traversed edges. Sometimes the words ''cost'' or ''length'' are used instead of weight. A simple path is one which contains no repeated vertices (in other words, it does not cross over itself). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Path (graph theory)」の詳細全文を読む スポンサード リンク
|